On va utiliser le fait que set-cover est un problème NP-complexe.

On construit un graphe avec des sommets auxilliaires qui permettent d'illustrer le problème.

Cela nous donne une équivalence entre "set-cover est réalisable" et "l'épidémie atteint \(k+N\) sommets", ce qui nous permet de conclure.

On a une écriture de l'ensemble des infectés.

On peut écrire cet ensemble comme une union d'ensembles sur \(A\).

Si on utilise cette écriture sur \(A\) et \(B\), alors l'union a la même définition.

Pour l'intersection cependant, on a une inclusion, qui génère une inégalité.

Cela permet de conclure via une inégalité.